package leetcode.pre100;


/**
 * <p>
 * 在8*8的国际象棋上拜访8个皇后，使其不能相互攻击，
 * 即任意两个皇后不得处在同一行、同一列或者同一对角线上。
 * 下图中的每个带有皇冠的格子表示一个皇后，这就是一种符合条件的摆放方法。
 * 请问总共有多少种符合条件的摆法？
 * <p>
 * 可以扩展到N皇后问题
 * <p>
 * 由于8个皇后的任意两个不能处在同一行，那么肯定是每一个皇后占据一行。
 * <p>
 * 于是我们可以定义一个数组ColumnIndex[8]，
 * 索引index就是第index个皇后，也就是第index行，不会重复的，不需要检查。
 * <p>
 * 对数组进行全排列 ,
 * 数值ColumnIndex[index]就是第index个皇后所处的列，
 * 任意一种排列结果都不会出现数字重复，所以不用检查列
 * <p>
 * 然后判断每一个排列对应的8个皇后是不是在同一对角线上，
 * 判断是否在同一对角线上： (a,b),(c,d)   |a-c| ?= |b-d|
 * 也就是对于数组的两个下标i和j，是不是|i - j |== |ColumnIndex[i] - ColumnIndex[j]|
 * <p>
 * 这种算法时间复杂度比较高，因为每次都是对排列好的数组进行验证，验证是O(n²).
 * 可以在全排列的过程中验证，不符合的就不用继续排了。见{@link Code51_Nqueen2}
 */
public class Code51_Nqueen1 {

    private static int totalCount = 0;

    public static void printNqueen(int n) {
        if (n <= 0) {
            return;
        }
        int[] array = new int[n];
        for (int i = 0; i < n; i++) {
            array[i] = i;
        }
        process(array, 0);
    }

    private static void process(int[] array, int index) {

        //全排列了一次,校验
        if (index == array.length - 1) {
//            System.out.println(Arrays.toString(leetcode.array));
            check(array);
        }
        //全排列
        for (int i = index; i < array.length; i++) {
            swap(array, i, index);
            process(array, index + 1);
            swap(array, index, i);
        }
    }

    private static void swap(int[] array, int i, int index) {
        int temp = array[i];
        array[i] = array[index];
        array[index] = temp;
    }

    //判断是否在同一对角线上，是的话，不满足条件
    //每个点都要和之前所有的点进行一一对比，是o(N²)
    private static boolean check(int[] array) {
        int len = array.length;
        for (int i = 0; i < len - 1; i++) {
            for (int j = i + 1; j < len; j++) {
                if (Math.abs(j - i) == Math.abs(array[j] - array[i])) {
                    return false;
                }
            }
        }
        totalCount++;
        print(array);
        return true;
    }

    //打印皇后摆法数量
    private static void print(int[] array) {
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + 1 + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {

        long start = System.currentTimeMillis();
        printNqueen(1);
        printNqueen(4);
        //12个用时14.431s
        System.out.println("用时 = " + (System.currentTimeMillis() - start));
        System.out.println("totalCount = " + totalCount);

    }

}
